#include "NVBRWalker.h"

NVBRWalker::NVBRWalker(const Image *pImage, F64 nRow, F64 nCol, F64 nAngle, Run runUp, Run runDown) : 
	View(pImage, nRow, nCol, nAngle),
	m_runUp(runUp), m_runDown(runDown), m_rf(this)
{}

bool NVBRWalker::CanWalk(U32 nSteps, bool bPathAllowedToEnd, Info *pInfo) {
	return CanWalkWorker(nSteps, 1, m_runUp, m_runDown, bPathAllowedToEnd, pInfo);
}

bool NVBRWalker::CanWalkWorker(U32 nSteps, S32 nCol, Run r, Run r2, bool bPathAllowedToEnd, Info *pInfo) {
	if (r.m_nStartPos == r2.m_nStartPos) abort();
	std::vector<Run> runVec;
	std::vector<Run> runVec2;
	S32 nRow; /* if we switch to really changing a view point, we won't need these */
	nRow = (S32)GetCenterRow();
	while(nSteps--) {
		runVec.clear();
		runVec2.clear();
		m_rf.GetAdjacentVertRuns(r, nCol, 0xFF, &runVec);
		m_rf.GetAdjacentVertRuns(r2, nCol, 0xFF, &runVec2);
		if (!runVec.size() || !runVec2.size()) {
			if (pInfo && bPathAllowedToEnd) {
				pInfo->m_r1 = r;
				pInfo->m_r2 = r2;
				pInfo->m_nCol = nCol - 1;
			}
			return bPathAllowedToEnd;
		} 
		if (runVec[runVec.size() - 1].m_nStartPos == runVec2[0].m_nStartPos)
			return false;
		/* if the bottommost run of the top runs and the topmost run of the bottom runs
		 * have to their right the same run, this means that they 
		 * (and all other runs that are to the left of that run)
		 * are NOT allowed to be used for our checks 
		 */
		Run commonRun = m_rf.GetCommonAdjacentVertRun
		                   (runVec[runVec.size() - 1], runVec2[0], nCol + 1, 0xFF);
		S32 nMaxTopRunsInd; // maximal index from all indices of top runs that are allowed to check 
		S32 nMinBottomRunsInd;
		if (!commonRun.m_nLength) /* there's no common run */ {
			nMaxTopRunsInd = runVec.size() - 1;
			nMinBottomRunsInd = 0;
		} else { /* there is a common run, so we get rid of runs that intersect with it */ 
			nMaxTopRunsInd = runVec.size() - 2;
			while(nMaxTopRunsInd >= 0 && 
			      runVec[nMaxTopRunsInd].EndPos() >= commonRun.m_nStartPos) {
				--nMaxTopRunsInd;
			}
			nMinBottomRunsInd = 1;
			while(nMinBottomRunsInd <= (S32)runVec2.size() - 1 &&
			      runVec2[nMinBottomRunsInd].m_nStartPos <= commonRun.EndPos()) {
				++nMinBottomRunsInd;
			}
			if (nMaxTopRunsInd < 0 || nMinBottomRunsInd > (S32)runVec2.size() - 1) {
				/* all the runs in one (or both) of the runVecs are unallowed */
				return false; 
			}
		}
		r = runVec[0];
		r2 = runVec2[runVec2.size() - 1];
		
		/* if there's more than one run in any of the vecs, we run the function
		 * recursively for the other cases 
		 */
		for(S32 i = nMaxTopRunsInd; i >= 0; --i) 
			for(S32 j = nMinBottomRunsInd; 
			    j < (i ? (S32)runVec2.size() : (S32)runVec2.size() - 1); ++j) 
				if (CanWalkWorker(nSteps, nCol + 1, runVec[i], runVec2[j], 
				                  bPathAllowedToEnd, pInfo))
					return true; 
		
		++nCol;
	}
/*	SetCenterCol(nCol);
	F64 nRow2, nCol2;
	nRow2 = ((m_runUp.m_nStartPos + m_runUp.m_nLength - 1) + m_runDown.m_nStartPos) / 2.0;
	nCol2 = nCol;
	TransformPoints(&nRow2, &nCol2);
	SetCenterRow(nRow2);
	SetCenterCol(nCol2);*/
	if (pInfo) {
		pInfo->m_r1 = r;
		pInfo->m_r2 = r2;
		pInfo->m_nCol = nCol - 1;
	}
	return true;
	
}
